package org.datacoder.geocoding.datastructures.rectangles

import org.datacoder.geocoding.*
import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.Jurisdiction

class LayeredSegmentTree implements RectanglesContainingPointFinder {

    public LayeredSegmentTreeNode root

    public LayeredSegmentTree(Collection<Jurisdiction> jurisdictions){
        SortedSet<Double> endPointSet = new TreeSet<Double>()
        Set<GeoInterval> geoIntervals = new HashSet<GeoInterval>()
        for(juris in jurisdictions){
            GeoInterval gi = juris.toGeoInterval(GeoShape.LON)
            geoIntervals.add(gi)
            endPointSet.add(gi.retrieveMinDoubleValue())
            endPointSet.add(gi.retrieveMaxDoubleValue())
        }
        double[] endPoints = new double[endPointSet.size()]
        Iterator iter = endPointSet.iterator()
        for(int i = 0; i < endPoints.length; i++){
            endPoints[i] = iter.next()
        }
        if(endPoints.length == 0){
            root = null
        }else{
            root = createNode(endPoints, 0, endPoints.length)
        }
        for(gi in geoIntervals){
            addGeoInterval(root, gi)
        }
        lock()
    }

    public LayeredSegmentTreeNode createNode(double[] endPoints, int startIndex, int endIndex){
        LayeredSegmentTreeNode lstNode = new LayeredSegmentTreeNode()
        lstNode.leftValue = endPoints[startIndex]
        lstNode.rightValue = endPoints[endIndex - 1]
        int middle = (startIndex + endIndex)/2
        if(startIndex < endIndex - 2){
            lstNode.left = createNode(endPoints, startIndex, middle + 1)
            lstNode.right = createNode(endPoints, middle, endIndex)
        }
        return lstNode
    }

    public void addGeoInterval(LayeredSegmentTreeNode lstNode, GeoInterval gi){
        if(gi.containsInterval(lstNode.leftValue, lstNode.rightValue)){
            lstNode.addJurisdiction(gi.juris)
        }else{
            if((lstNode.left != null) && gi.intersectsInterval(lstNode.left.leftValue, lstNode.left.rightValue)){
                addGeoInterval(lstNode.left, gi)
            }
            if((lstNode.right != null) && gi.intersectsInterval(lstNode.right.leftValue, lstNode.right.rightValue)){
                addGeoInterval(lstNode.right, gi)
            }
        }
    }

    public void lock(){
        Queue<LayeredSegmentTreeNode> lstNodeQueue = new LinkedList<LayeredSegmentTreeNode>()
        lstNodeQueue.offer(root)
        while(lstNodeQueue.peek() != null){
            LayeredSegmentTreeNode currentNode = lstNodeQueue.poll()
            currentNode.lock()
            if(currentNode.left != null){
                lstNodeQueue.offer(currentNode.left)
            }
            if(currentNode.right != null){
                lstNodeQueue.offer(currentNode.right)
            }
        }
    }

    public Set<Jurisdiction> findRectanglesContainingPoint(GeoPoint gp){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        if(!root.containsPoint(gp.lon)){
            return jurisdictions
        }
        Queue<LayeredSegmentTreeNode> lstNodeQueue = new LinkedList<LayeredSegmentTreeNode>()
        lstNodeQueue.offer(root)
        while(lstNodeQueue.peek() != null){
            LayeredSegmentTreeNode currentNode = lstNodeQueue.poll()
            jurisdictions.addAll(currentNode.findRectanglesContainingPoint(gp))
            if((currentNode.left != null) && (currentNode.left.containsPoint(gp.lon))){
                lstNodeQueue.offer(currentNode.left)
            }
            if((currentNode.right != null) && (currentNode.right.containsPoint(gp.lon))){
                lstNodeQueue.offer(currentNode.right)
            }
        }
        return jurisdictions
    }

}

